home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / graphics / qrt.lzh / INTERSECT.C < prev    next >
C/C++ Source or Header  |  1989-02-16  |  13KB  |  488 lines
  1.  
  2. /**********************************************************
  3.  
  4.   Line/Object intersection routines.  Routine returns
  5.   TRUE if object is hit, along with the nearest of the
  6.   possibly multiple intersections.  First parameter is
  7.   line, second is object, and third is pointer to parameter
  8.   on line for intersection (filled by routine).  Functions
  9.   are pointed at by entries in ObjData structure.
  10.  
  11.  **********************************************************/
  12.  
  13. #include "qrt.h"
  14.  
  15. /* #define INTERSECTDEBUG */
  16.  
  17. /**********************************************************
  18.  
  19.           Line/bounding box intersection test.
  20.  
  21.    Looks bad, but its pretty fast.  Many times we don't
  22.    even have to go through the whole routine if a miss
  23.    can be detected early.
  24.  
  25.  **********************************************************/
  26.  
  27. int LineBbox(line, bbox, t)
  28.   OBJ_PTR line, bbox;
  29.   float *t;
  30. {
  31.   register float tminx, tmaxx, tminy, tmaxy,
  32.                  tminz, tmaxz, tmin, tmax, t1,t2;
  33.  
  34.   *t=10;
  35.  
  36. # ifdef ROBUST
  37.     if (line->type!=LINE) Error(INTERNAL_ERROR,301);
  38.     if (bbox->type!=BBOX) Error(INTERNAL_ERROR,302);
  39. # endif
  40.  
  41.   if (fabs(line->vect1.x) < SMALL) {
  42.     if ((bbox->lower.x < line->loc.x) &&
  43.         (bbox->upper.x > line->loc.x)) {
  44.           tminx = -3e30; tmaxx=3e30;
  45.         } else return(FALSE);
  46.  
  47.   } else {
  48.     t1 = (bbox->lower.x-line->loc.x)/line->vect1.x;
  49.     t2 = (bbox->upper.x-line->loc.x)/line->vect1.x;
  50.     tminx = MIN(t1,t2);
  51.     tmaxx = MAX(t1,t2);
  52.     if (tmaxx<0) return(FALSE);
  53.   }
  54.  
  55.   if (fabs(line->vect1.y) < SMALL) {
  56.     if ((bbox->lower.y < line->loc.y) &&
  57.         (bbox->upper.y > line->loc.y)) {
  58.           tminy = -3e30; tmaxy=3e30;
  59.         } else return(FALSE);
  60.  
  61.   } else {
  62.     t1 = (bbox->lower.y-line->loc.y)/line->vect1.y;
  63.     t2 = (bbox->upper.y-line->loc.y)/line->vect1.y;
  64.     tminy = MIN(t1,t2);
  65.     tmaxy = MAX(t1,t2);
  66.     if (tmaxy<0) return(FALSE);
  67.   }
  68.  
  69.   if (fabs(line->vect1.z) < SMALL) {
  70.     if ((bbox->lower.z < line->loc.z) &&
  71.         (bbox->upper.z > line->loc.z)) {
  72.           tminz = -3e30; tmaxz=3e30;
  73.         } else return(FALSE);
  74.  
  75.   } else {
  76.     t1 = (bbox->lower.z-line->loc.z)/line->vect1.z;
  77.     t2 = (bbox->upper.z-line->loc.z)/line->vect1.z;
  78.     tminz = MIN(t1,t2);
  79.     tmaxz = MAX(t1,t2);
  80.     if (tmaxz<0) return(FALSE);
  81.   }
  82.  
  83.   tmin = MAX(MAX(tminx,tminy),tminz);
  84.   tmax = MIN(MIN(tmaxx,tmaxy),tmaxz);
  85.  
  86. # ifdef INTERSECTDEBUG
  87.     printf("LINEBBOX: dir = %f %f %f\n",line->vect1.x,
  88.                                         line->vect1.y,
  89.                                         line->vect1.z);
  90.  
  91.     printf("  tminx=%7.2f, tmaxx=%7.2f, tminy=%7.2f, tmaxy=%7.2f\n",
  92.             tminx, tmaxx, tminy, tmaxy);
  93.     printf("  tminz=%7.2f, tmaxz=%7.2f, tmin=%7.2f,  tmax=%f\n",
  94.             tminz, tmaxz, tmin, tmax);
  95. # endif
  96.  
  97.   if (tmax<0) return(FALSE);
  98.  
  99.   if (tmax<tmin) return(FALSE);
  100.  
  101. # ifdef INTERSECTDEBUG
  102.     printf("  HIT:\n");
  103. # endif
  104.  
  105.   return(TRUE);
  106. }
  107.  
  108. /**********************************************************
  109.  
  110.                Line/ring intersection test
  111.  
  112.      Similar to, but slower than parallelogram test
  113.  
  114.  **********************************************************/
  115.  
  116. int LineRing(line, ring, t)
  117.   OBJ_PTR line, ring;
  118.   float *t;
  119. {
  120.   VECTOR         delta, loc;
  121.   register float dot, rad, pos1, pos2;
  122.  
  123. # ifdef ROBUST
  124.     if (line->type!=LINE) Error(INTERNAL_ERROR,303);
  125.     if (ring->type!=RING) Error(INTERNAL_ERROR,304);
  126. # endif
  127.  
  128.   dot  = DotProd((ring->precomp.norm),line->vect1);
  129.  
  130.   if (fabs(dot)<SMALL) return(FALSE);
  131.  
  132.   pos1 = ring->precomp.n1;
  133.   pos2 = DotProd((ring->precomp.norm),line->loc);
  134.  
  135.   *t=(pos1-pos2)/dot;
  136.  
  137. # ifdef INTERSECTDEBUG
  138.     printf("LINERING: t=%f\n", *t);
  139. # endif
  140.  
  141.   FindPos(&loc,line,*t);
  142.   VecSubtract(&delta,&loc,&(ring->loc));
  143.  
  144.   pos1 = DotProd(delta,ring->vect1);
  145.   pos2 = DotProd(delta,ring->vect2);
  146.  
  147.   rad = sqrt(sqr(pos1)+sqr(pos2));
  148.  
  149. # ifdef INTERSECTDEBUG
  150.     printf("LINERING  pos1,2 = %f %f\n",pos1,pos2);
  151.     printf("          radius = %f\n",rad);
  152.     printf("          R1,2   = %f %f\n",ring->vect3.x,ring->vect3.y);
  153. # endif
  154.  
  155.   if (rad<(ring->vect3.x) || rad>(ring->vect3.y))
  156.      return(FALSE);
  157.  
  158. # ifdef INTERSECTDEBUG
  159.     printf("  HIT:\n");
  160. # endif
  161.  
  162.   return(TRUE);
  163. }
  164.  
  165.  
  166. /**********************************************************
  167.  
  168.         Line/Parallelogram intersection test
  169.         Returns Parameter T for intersection
  170.  
  171.  **********************************************************/
  172.  
  173. int LineParallelogram(line, para, t)
  174.   OBJ_PTR line, para;
  175.   float *t;
  176. {
  177.   VECTOR         delta, loc;
  178.   register float dot, in1, in2;
  179.  
  180. # ifdef ROBUST
  181.     if (line->type!=LINE)          Error(INTERNAL_ERROR,305);
  182.     if (para->type!=PARALLELOGRAM) Error(INTERNAL_ERROR,306);
  183. # endif
  184.  
  185.   dot = DotProd((para->precomp.norm),line->vect1);
  186.  
  187.   if (fabs(dot)<SMALL) return(FALSE);
  188.  
  189.   in1 = para->precomp.n1;
  190.   in2 = DotProd((para->precomp.norm),line->loc);
  191.  
  192.   *t=(in1-in2)/dot;
  193.  
  194. # ifdef INTERSECTDEBUG
  195.     printf("LINEPARALL: t=%f\n", *t);
  196. # endif
  197.  
  198.   FindPos(&loc,line,*t);
  199.   VecSubtract(&delta,&loc,&(para->loc));
  200.  
  201.   in1  = DotProd(delta,para->vect1)/(para->precomp.len1);
  202.   in2  = DotProd(delta,para->vect2)/(para->precomp.len2);
  203.  
  204. # ifdef INTERSECTDEBUG
  205.     printf("LINEPARALL: in1,2 = %f %f\n",in1,in2);
  206. # endif
  207.  
  208.   if (!((in1>=0) && (in2>=0) && (in1<=1) && (in2<=1)))
  209.     return(FALSE);
  210.  
  211. # ifdef INTERSECTDEBUG
  212.     printf("  HIT:\n");
  213. # endif
  214.  
  215.   return(TRUE);
  216. }
  217.  
  218.  
  219. /**********************************************************
  220.  
  221.         Line/Triangle intersection test
  222.         Returns Parameter T for intersection
  223.  
  224.  **********************************************************/
  225.  
  226. int LineTriangle(line, obj, t)
  227.   OBJ_PTR line, obj;
  228.   float *t;
  229. {
  230.   VECTOR         delta, loc;
  231.   register float dot, in1, in2;
  232.  
  233. # ifdef ROBUST
  234.     if (line->type != LINE)      Error(INTERNAL_ERROR,307);
  235.     if (obj->type  != TRIANGLE)  Error(INTERNAL_ERROR,308);
  236. # endif
  237.  
  238.   dot = DotProd((obj->precomp.norm),line->vect1);
  239.  
  240.   if (fabs(dot)<SMALL) return(FALSE);
  241.  
  242.   in1 = obj->precomp.n1;
  243.   in2 = DotProd((obj->precomp.norm),line->loc);
  244.  
  245.   *t=(in1-in2)/dot;
  246.  
  247. # ifdef INTERSECTDEBUG
  248.     printf("LINEPARALL: t=%f\n", *t);
  249. # endif
  250.  
  251.   FindPos(&loc,line,*t);
  252.   VecSubtract(&delta,&loc,&(obj->loc));
  253.  
  254.   in1  = DotProd(delta,obj->vect1)/(obj->precomp.len1);
  255.   in2  = DotProd(delta,obj->vect2)/(obj->precomp.len2);
  256.  
  257. # ifdef INTERSECTDEBUG
  258.     printf("LINETRIANGLE: in1,2 = %f %f\n",in1,in2);
  259. # endif
  260.  
  261.   if (!((in1>=0) && (in2>=0) && (in1+in2<=1)))
  262.     return(FALSE);
  263.  
  264. # ifdef INTERSECTDEBUG
  265.     printf("  HIT:\n");
  266. # endif
  267.  
  268.   return(TRUE);
  269. }
  270.  
  271.  
  272. /**********************************************************
  273.  
  274.            Line/sphere intersection test
  275.         Returns parameter T for intersection
  276.  
  277.  **********************************************************/
  278.  
  279. int LineSphere(line, sph, t)
  280.   OBJ_PTR line, sph;
  281.   float *t;
  282. {
  283.   register float a,b,c,d,t1, tmpx,tmpy,tmpz;
  284.  
  285. # ifdef ROBUST
  286.     if (line->type!=LINE) Error(INTERNAL_ERROR,309);
  287.     if (!(sph->type==SPHERE || sph->type==LAMP))
  288.       Error(INTERNAL_ERROR,310);
  289. # endif
  290.  
  291.   tmpx = sph->loc.x-line->loc.x;
  292.   tmpy = sph->loc.y-line->loc.y;
  293.   tmpz = sph->loc.z-line->loc.z;
  294.  
  295.   c = sqr(tmpx)+ sqr(tmpy)+ sqr(tmpz) - (sph->precomp.n1);
  296.  
  297.   b = -2*(line->vect1.x*tmpx+                      /* find b */
  298.           line->vect1.y*tmpy+
  299.           line->vect1.z*tmpz);
  300.  
  301.   a = sqr(line->vect1.x)+                          /* find a */
  302.       sqr(line->vect1.y)+
  303.       sqr(line->vect1.z);
  304.  
  305.   d = sqr(b)-4.0*a*c;
  306.  
  307. # ifdef INTERSECTDEBUG
  308.     printf("LINESPHERE: a=%f, b=%f, c=%f, d=%f\n",a,b,c,d);
  309. # endif
  310.  
  311.   if (d<=0) return(FALSE);                          /* does sphere hit? */
  312.  
  313.   d=sqrt(d); *t=(-b+d)/(a+a);
  314.              t1=(-b-d)/(a+a);
  315.  
  316.   if (t1<*t && t1>SMALL) *t=t1;                     /* find 1st collision */
  317.  
  318.   if (*t > SMALL) {
  319.  
  320. #   ifdef INTERSECTDEBUG
  321.       printf("LINESPHERE: collision @ t=%f\n",*t);
  322. #   endif
  323.  
  324.     return(TRUE);
  325.   }
  326.  
  327.   return(FALSE);
  328. }
  329.  
  330. /**********************************************************
  331.  
  332.         Line/quadratic intersection test
  333.         Returns parameter T for intersection
  334.  
  335.   newline is the input line translated and rotated so that
  336.   the quadratic is @ 0,0,0 and pointed up.
  337.  
  338.  **********************************************************/
  339.  
  340. int LineQuadratic(line, quad,